package simple;

import org.junit.Test;

/**
 * 14. 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * <p>
 * 如果不存在公共前缀，返回空字符串 ""。
 * <p>
 * 示例 1:
 * <p>
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * 示例 2:
 * <p>
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 * 说明:
 * <p>
 * 所有输入只包含小写字母 a-z 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Chen Wei
 * @date 2020-11-17 15:49
 */
public class No14LongestCommonPrefix {
    /**
     * 1 横向扫描
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    public String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }

    /**
     * 2 纵向扫描
     * @param strs
     * @return
     */
    public String longestCommonPrefix2(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        // 第一个字符串的长度
        int length = strs[0].length();
        // 字符串数组的长度
        int count = strs.length;
        // 遍历第一个字符串
        for (int i = 0; i < length; i++) {
            // 获取第一个字符串的每个字符
            char c = strs[0].charAt(i);
            // 遍历第二个字符串以后续的字符串
            for (int j = 1; j < count; j++) {
                // 判断 第一个字符数组的索引i是否与第j个字符串的长度相等
                // 或 获取第j个字符串的第i个字符串是否与第一个字符串的第i个字符相同
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    // 获取第一个字符串的0到i位作为子字符串
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    /**
     *  3 分治法
     * @param strs
     * @return
     */
    public String longestCommonPrefix3(String[] strs) {
        if (strs != null && strs.length == 0) {
            return "";
        } else {
            return longestCommonPrefix3(strs, 0, strs.length - 1);
        }
    }

    public String longestCommonPrefix3(String[] strs, int start, int end) {
        if (start == end) {
            return strs[start];
        } else {
            int mid = (end - start) / 2 + start;
            // 迭代分治
            String lcpLeft = longestCommonPrefix3(strs, start, mid);
            String lcpRight = longestCommonPrefix3(strs, mid + 1, end);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    public String commonPrefix(String lcpLeft, String lcpRight) {
        int minLength = Math.min(lcpLeft.length(), lcpRight.length());
        for (int i = 0; i < minLength; i++) {
            if (lcpLeft.charAt(i) != lcpRight.charAt(i)) {
                return lcpLeft.substring(0, i);
            }
        }
        return lcpLeft.substring(0, minLength);
    }

    @Test
    public void test1() {
        String[] strs = new String[]{"flower","flow","flight"};
        String longestCommonPrefix = longestCommonPrefix(strs);
        System.out.println(longestCommonPrefix);
    }

    @Test
    public void test2() {
        String[] strs = new String[]{"flower","flow","flight"};
        String longestCommonPrefix = longestCommonPrefix2(strs);
        System.out.println(longestCommonPrefix);
    }

    @Test
    public void test3() {
        String[] strs = new String[]{"flower","flow","flight"};
        String longestCommonPrefix = longestCommonPrefix3(strs);
        System.out.println(longestCommonPrefix);
    }
}
